               README for Tradewars 2002 bubble finder v0.14


                  Contents ..........................  1

               I. Legal Stuff .......................  2

              II. Overview ..........................  2
    
             III. Getting Sector Data ...............  3

              IV. Running the Program ...............  6

               V. Output ............................  9

              VI. Limitations .......................  11
 
             VII. Performance .......................  11

            VIII. Notes on Program Behavior .........  12

              IX. How it Works ......................  13
                                                       
               X. Compiling the Program .............  14 

              XI. Author Information ................  15

             XII. History ...........................  15





























                                   Page 1
I. Legal Stuff

This program is provided free of charge, and I'm not liable for any damage 
it may do, nor do I guarantee any level of functionality.  You know the 
drill.

If you make any modifications, I require that you make an effort to contact 
me before distributing the modified form.  

================================================================================

II. Overview

If you don't play the BBS online door game Tradewars 2002, then you'll find 
this particular program quite useless indeed.

If you do play, however, you may find it extremely useful.  

You may still, however, not be sure what a "bubble" in the game is.  

If you've been playing for any amount of time, you've probably come to 
realize what a tunnel is, specifically, an arrangement of sectors something 
like this:

3343
     \
2231 - 556 - 783 - 3259 - 895
     /
1011

In this case, 895 would be a dead-end sector.  Only one way in, and one 
way out.  The more sectors like 783 and 3259 between it and 556, the better.

The helper program that I use, Trade Wars Helper version 8.8, is able to 
find tunnels like the above, but it's not able to handle something like 
this:

3343               4490
     \              |
2231 - 556 - 783 - 3259 - 895
     /              |
1011               2333

TW Helper would report the above as three one-sector tunnels, whereas in 
reality is is a 5-sector bubble, with the entrance at 556.

There are two other helper programs that I know of out there, entitled TWar 
and TWATS.  TWar claims to be able to find "tunnels" with non-sequential 
sectors (which apparently covers the above), and TWATS claims to be able to 
find large bubbles.  And for all I know, they both do the job very nicely 
indeed.  But the evaluation versions are too crippled to test this feature, 
and I see no compelling reason to pay for either one, since they appear to 
do nothing that TW Helper doesn't do as well or better.  

Except for the bubble finding, of course.  After spending about 5 seconds 
deciding that TW Helper's /I and /G commands together would take too much 

                                   Page 2
time, I set out to write a program that would find bubbles automatically.

It was quite a learning experience, and it's still possible that there's 
more that I haven't thought of which will make it into a future version.

Something new to the program is finding bubbles with more than one 
entrance.  Something like the following:


3343               4490                            3234
     \              |                            /
2231 - 556 - 783 - 3259 - 895 - 443 - 559 - 1235 - 4454
     /              |               \            \
1011               2333               990 - 784    1903

The entrances in the above would be 556 and 1235.  It shouldn't take much 
imagination to see how more entrances would fit in.

See notes on program behavior for caveats with multiple-entrance bubbles.

New to versions 0.13 and later is the ability to use CIM course plot
captures, which is what helper programs use to do zero-turn mapping.  What
these captures provide is the route between one sector and another.  For
each sector in the route, it tells us two things:

    1)  The sector in question has an outwarp to the next sector in the
        route.

    2)  The sector in question has an inwarp from the previous sector in
        the route.

With enough course plots, you can get complete information about a sector
without exploring it.

See the notes on program behavior for the potential downside to this
ability (which is why it can be avoided altogether or disabled).

================================================================================

III. Getting Sector Data

Starting with version 0.13, the program can acquire data from three
sources:

    1) Binary database.
    2) CIM course plot session capture.
    3) CIM sector information.

You can use any one of the above, or any combination of them.  They are
read in the order listed above, to make the last information read the most
accurate.  The binary database, of course, is created by a previous run of
the program, which used either or both of the CIM captures for input.

Details on the different files:

1) Binary database - this file is created by TWBFind, if you specify a

                                   Page 3
binary file name on the command line.  The data is written after reading in
any data from the other two file formats.  The file consists of 16 bytes of
data for every sector.  There are two bytes each for the maximum of six
outwarps, an explored byte, and three reserved bytes. A typical hex editor
will show you one sector per line, with a smily face in the first column
from the left indicating that it's explored.

2)  CIM course plot session capture - this file is created by you, using
your communications program with a script.  How exactly you do this will
vary, of course.  In your comm script, you'll want to enter CIM mode (see
below), and plot various courses, which will show how sectors are
connected.  Plots are done by pressing "F", then entering the start and end
sectors.

The more plots, the more information.  The only way to get all information
without exploring is to plot a course from each sector to every other
sector, and back again.  In a universe with just 1000 sectors, this means
998,000 plots.  With 5000 sectors, it's 24,990,000 plots.  And with 20,000
sectors, you'd need to do 399,960,000 plots.  Needless to say, doing all
those plots would be time consuming.  So time consuming, in fact, that
actually exploring the universe would take less time.

So, what you're looking for is a way to get a lot of warp information in
relatively few course plots.  The simplest way to do this is by using a
simple algorithm that picks two sectors, and plots a course in both
directions, where every sector is covered at least once.  A few options:

    a.  Pick one sector, and plot a course from it to and back from every
        other sector in the universe - 1 > 5000; 5000 > 1; 1 > 4999;
        4999 > 1; etc.  This takes N*2-2 plots, where N is the number of
        sectors in the univers.

    b.  Do plots between numerically adjacent sectors - 5000 > 4999;
        4999 > 5000; 4999 > 4998; 4998 > 4999; etc.  This takes N plots.

    c.  Work from the outside in - 1 > 5000; 5000 > 1; 2 > 4999; 4999 > 2;
        3 > 4998; 4998 > 3; etc.  This also takes N plots.

Method (a) is the least effective of the three, even though it does twice
as many plots as the other two (and hence, takes twice as long to perform
as the other two).  Methods (b) and (c) are about equally effective, though
they will each discover warps that the other did not.

I did each of these plots in both 5000-sector and 20000-sector universes.
Method (a) was done with sector 1 as the base (using that, or the stardock
sector is common - it really doesn't much matter).  Methods (b) and (c), of
course, have no base.

The following chart of warps shows the results:

          -----------------------------------------------------------------
          |          5,000 Sectors        |         20,000 Sectors        |
---------------------------------------------------------------------------
| Method  |   Found  |  Actual  |    %    |   Found  |   Actual |    %    |
--------------------------------------------------------------------------
|   (a)   |   9,756  |  13,489  |  72.33  |  38,789  |  53,835  |  72.05  |

                                   Page 4
|   (b)   |  12,971  |     "    |  96.16  |  52,162  |     "    |  96.89  |
|   (c)   |  12,956  |     "    |  96.05  |  52,155  |     "    |  96.88  |
| (a)+(b) |  13,291  |     "    |  98.53  |  53,125  |     "    |  98.68  |
| (a)+(c) |  13,285  |     "    |  98.49  |  53,116  |     "    |  98.66  |
| (b)+(c) |  13,395  |     "    |  99.30  |  53,503  |     "    |  99.38  |
|   all   |  13,443  |     "    |  99.66  |  53,637  |     "    |  99.63  |
---------------------------------------------------------------------------

As you can see, method (a) is indeed the least effective, while methods (b)
and (c) are indeed basically the same.  Combining methods (b) and (c) gives
you virtually all of the warps in the universe, though you can still do
better by adding method (a).  At that point, any additional plots will
provide increasingly diminishing returns.

For more perspective, I did a bubble search with the varying amounts of
data, using a minimum size of 3, maximum size of 25, and the /t option.
The following chart shows how the various plots and their combinations
faired in accurately finding bubbles:

          -----------------------------------------------------------
          |       5,000 Sectors        |        20,000 Sectors      |
---------------------------------------------------------------------
| Method  |  Found | Actual | % Error  |  Found | Actual | % Error  |
---------------------------------------------------------------------
|   (a)   |   404  |   62   |  551.61  |  1533  |  200   |  666.50  |
|   (b)   |    95  |    "   |   53.23  |   338  |    "   |   69.00  |
|   (c)   |    96  |    "   |   54.84  |   335  |    "   |   67.50  |
| (a)+(b) |    74  |    "   |   19.35  |   251  |    "   |   25.50  |
| (a)+(c) |    72  |    "   |   16.13  |   239  |    "   |   19.50  |
| (b)+(c) |    62  |    "   |    0.00  |   211  |    "   |   05.50  |
|   all   |    62  |    "   |    0.00  |   205  |    "   |   02.50  |
---------------------------------------------------------------------

As you can see, with method (1), you'll find five times or more as many
bubbles as actually exist.    Methods (b) and (c) give you half as many
more than actually exist with 5,000 sectors, and even more with 20,000
sectors.  Once you start combining, the picture looks much better.  With
5,000 sectors, methods (b) and (c) combined find no invalid bubbles.  With
20,000 sectors, they find just 11.  Adding in method (a) will probably be
unnecessary for a 5,000 sector (or smaller) universe.  But with the 20,000
sector universe, it halves the number of incorrect bubbles found.

In general, combining methods (b) and (c) will give you fairly reliable
information, decreasing in reliability as the size of the universe
increases, with the same number of plots performed as a single run of
method (a).  If you've got the time, doing all three is best (and with
larger universes, finding a new simple algorithm to add reliability would
be good, too).

3)  CIM sector information - this file is also created by you, but is just
a simple capture of what the game spits out.  To make this file, turn the
capture mode of your comm program on, enter CIM mode (see below), and press
"I".  After the scrolling display of sector information has stopped, stop
the capture.  That capture file can be used as is by TWBFind.

To enter CIM mode in Tradewars 2002, go to the ship computer, and enter the

                                   Page 5
following sequence, using your numeric keypad (on the right side of the
keyboard):

ALT-200
ALT-201
ALT-202
ALT-203
ALT-204
ALT-205

If you didn't mess up, you'll be met with a plain looking ":" for a prompt.

From here, you can enter the CIM commands necessary to get data.

================================================================================

IV. Running the Program

Once you've exported the sector data from the game, you're ready to run the 
program. 

The options are available by simply running the program without parameters, 
or with /h or /?, and are as follows:

/a  - avoid unexplored sectors when finding bubbles
/t  - use only one bubble route from primary entrance
/u  - update binary database only - don't do a bubble search
/f  - find fake bubbles (one-way sectors in)
/g  - gobble memory to increase speed during search
/m# - minimum number of sectors in bubble; default 5
/x# - maximum number of sectors in bubble; default 50
/n# - number of sectors in universe (100 to 65535); default 1000
/e# - maximum number of entrances for bubbles (1 to 50); default 1
/z# - entrance multiplier for minimum bubble size (2.0 to 1000.0); default 2.0
/r# - reserve storage for this many bubbles (1 to 4.3 billion); default 1024
/p# - priority class (1 to 4); default=2 [OS/2 only]
/d# - priority delta (-31 to 31); default=-31 [OS/2 only]
/s<filename> - sector data file
/b<filename> - binary sector database file
/c<filename> - second binary database to combine info with
/w<filename> - CIM course plot capture file
/o<filename> - report file; default 'bubbles.lst'

Detailed explanations:

Option /a:  This tells the program to consider all unexplored sectors to be
unreliable, whether or not any outwarps are defined for them (from CIM
course plots).  The default behavior is to consider a sector's information
to be reliable for the purposes of finding bubbles, if it has at least one
outwarp defined.  This is to utilize CIM course plot data for zero-turn
mapping.  Since you can store this information in a binary database, this
option allows you to do only bubble searches with explored sectors, to get
more accurate results (searches based on zero-turn mapping data are
potentially unreliable - depending on what methods you use).

Option /t:  When this option is used, the program doesn't consider all 

                                   Page 6
combinations of the bubble entrance's warps as either ways back to the 
universe, or parts of the potential bubble.  Instead, it will consider only 
one warp at a time as part of the potential bubble, with all other sectors 
as ways back to the universe.  This reduces the number of iterations, 
decreasing runtime, and also prevents the situation described in the second 
note on program operation.

Option /u:  Use this to avoid doing a bubble search, and only update the
specified binary sector database with new information, from either a
standard CIM sector info file, or a CIM course plot capture.

Option /f:  Use this switch to find only bogus bubbles, which appear good
from the inside, but have a one-way sector leading into them from behind
the entrance.  This data will be useful for finding enemies who weren't
very careful about checking their bubble.  Those with the one-way entrance
far back in the bubble will be especially good, since the least-defended
planets will likely be in those "safer" sectors.  When this option is used,
*only* bogus bubbles will be found and reported.  The bubble data file will
clearly mark them as such.

Option /g:  This switch tells the program to use fixed-length arrays for
bubble data, rather than dynamically extended ones.  That is, instead of
expanding the arrays as necessary to add new sectors and entrances, enough
space to accomodate the maximum number of sectors and entrances for the
current search is allocated when the bubble is initialized.  This makes the
search operation faster, at the expense of requiring more memory during
operation.  With /M3 /X100 /E4 /Z3 on a 5000-sector universe (502 potential
bubbles, 172 actual), the result is 116KB more memory required, with a 20%
increase in speed.  This option should be used cautiously with the DOS
version.

Option /m#:  This specifies the minimum number of sectors that a bubble 
must contain to be saved and reported.  When dead ends have been reached 
while traversing the potential bubble, if the number of sectors found 
(minus the number of entrances) is less than this number, the bubble is 
scrapped.  The default value is 5 sectors.

Option /x#:  This specifies the maximum number of sectors to traverse while 
searching for a bubble, before giving up and assuming that it's a lost 
cause.  If the number of sectors in a bubble (not counting the entrances) 
exceeds this number before all dead ends are reached, the potential bubble 
is scrapped.  The larger the number, the more potential bubbles you can 
find, but the longer the program takes to run.  Using the default will 
probably be fine for any standard game.  With Gold games, you should try a 
larger number, with multiple entrances, to find the bubble structures that 
the Gold-enabled Big Bang can be configured to create.  The largest such 
structure can be up to 19900 sectors, in a 20000-sector universe with one 
bubble allowed, so consider that when choosing this number in a Gold game.  
The default value is 50 sectors.

Option /n#:  This specifies the number of sectors in the universe.  Here is 
where the amount of storage set aside for sector information is determined.  
If the CIM file contains information for a sector number greater than this 
value, the program will abort.  The maximum value that the DOS version will 
support is 16382.  The OS/2 and DPMI versions support up to 65535 sectors
(currently, TW Gold supports only 20000 sectors).  The default value is 

                                   Page 7
1000 sectors.

Option /e#:  This specifies the number of entrances that the bubble may 
have.  There's no theoretical limit (that's less than the number of 
sectors, anyway), but practicality prompted me to put in a somewhat 
arbitrary limit of 50 entrances.  This will allow one to locate the large 
bubble structures in Gold games, which can have many entrances.  The 
default value is 1 entrance.

Option /z#:  This specifies how many sectors a bubble must contain relative 
to the number of entrances for it to be saved.  If the current bubble can 
be saved with 3 entrances, for example, and the value for this option is 
set to 3, then the bubble must have at least nine non-entrance sectors to 
actually be saved.  The default and minimum value is 2.  The maximum value 
is 1000 (which would, say, require 3000 sectors for a 3-entrance bubble).  
Fractional numbers are allowed, so you can specify 2.5, 7.2, etc.

Option /r#:  Use this to specify a maximum number of bubbles other than the
default of 1024.  This number represents the maximum number of potential
bubbles that will be found before the search is terminated, and those found
trimmed and reported.  How much memory is reserved depends on the memory
model of your system.  The included executables all use 4 bytes to store a
memory pointer, so the default value reserves 4KB of memory.  A 64-bit flat
addressing model would reserve 8 bytes per bubble, or 8KB of memory.
Memory-constrained DOS systems may want to specify a value lower than 1024
here, to maximize the amount of memory available for the search.  For a
search with a 5000-sector universe using /M3, with all else default, 256
would be a safe value (which uses 3KB of memory less than the default).

Option /p#:  This is specific to the OS/2 version, and specifies the 
priority class that the program runs in while searching for bubbles.  
Allowable values are integers from 1 to 4, where 1 denotes idle-class, 2 
denotes standard class, 3 denotes time-critical class, and 4 denotes 
foreground-server class.  The order of precedence, from lowest priority to 
highest, is 1-2-4-3.  This is only put into effect after the sector 
information has been loaded, and the bubble search has begun.  The idea 
here was to be able to run the program at idle priority in the background 
for a long search (for very large bubbles), while doing other things.  If 
you specify a value of 3, which is the highest priority, then a timeslice 
will be forfeited every 100 sectors, to allow you the chance to abort it 
(otherwise, keyboard input won't be processed in a timely fashion).  The 
result is that the program will run somewhat slower at time-critical 
priority than otherwise, unless there are other high-priority programs that 
are being unfriendly to the CPU.  The default value is 2.

Option /d#:  This is specific to the OS/2 version, and specifies the 
priority delta value.  This is a subdivision of the priority class, with 
valid values from 0 to 31.  Giving a value above 0 will put the priority
slightly above other such programs, making this program run somewhat faster
if other CPU-intensive tasks are running.  The default value is 0.

Option /s<filename>:  This specifies the name of the file which contains 
the CIM data capture.  Either this option, or one of the following two
options must be used.

Option /b<filename>:  This specifies the name of the binary database file,

                                   Page 8
which will be created after reading other sector information in, and read
from if it exists beforehand.  This is always optional, though it's a good
idea to use.  If no database exists, and you don't specify other methods of
reading sector information, the program will abort with an error.

Option /c<filename>:  This specifies the name of an auxiliary binary
database file, which will have its contents read in, combined with existing
data, and written out to the primary binary database file.  That is, if you
use it as it was designed.  Since it's easier to deal with this way, you
can also use this simply as an additional input file format, without
specifying a binary database to which changes should be made.  The main
usage you should have for this is in combination with the /U switch, to
combine two databases from different sources (CIM sector data, one or more
CIM course plots).

Option /w<filename>:  This specifies the name of the CIM course plot file,
which is a capture of any number of course plots you made with a comm
program script.  This is useful for finding potential bubbles before
actually exploring, to get a head start in the game.

Option /o<filename>:  This specifies the name of the file which the found 
bubbles will be written to.  The specified file will be overwritten if it 
exists.  You may also use anything which the operating system can handle as 
a file, such as a named pipe, communications port, network printer name, 
etc.  The default is "bubbles.lst".

There is no space between the switch and the option data, so assuming a 
sector data file of "sectors.txt", you might do the following:

twbfind.exe /ssectors.txt /m4 /x20 /n5000 /obubbles.txt

This would read in the sector data from "sectors.txt", search for bubbles 
with a minimum of 4 sectors, and a maximum of 20 sectors, then write them 
to "bubbles.txt".

=============================================================================

V. Output

Since all output is accomplished via stream I/O, you can use anything that 
the underlying operating system can open as a file for output.  This 
includes I/O devices, such as LPT1, CON, etc.

The format of the output is this:

12-sector bubble with entrance at 2381.

Sectors in bubble:
 4051   4230   3764   2107   847   2524   2657   2683   3579   3759  
 1740   3936  

Sector  2381  -     110    1818    4051    4230  
Sector  4051  -  { 2381}  3764  
Sector  4230  -  { 2381}
Sector  3764  -    2107    4051  
Sector  2107  -     847    3764  

                                   Page 9
Sector   847  -    2107    2524    2657    2683  
Sector  2524  -     847  
Sector  2657  -     847    3579  
Sector  2683  -     847    3759  
Sector  3579  -    1740    2657  
Sector  3759  -    2683    3936  
Sector  1740  -    3579  
Sector  3936  -    3759  

--------------------------------------------------------------------------------

11-sector bubble with 2 entrances at:
  4310  3901

Sectors in bubble:
 4374   91   1846   4258   4309   3537   3230   919   2314   4505  
 3186  

Sector  4310  -  < 3975>   3439    4134    4374  
Sector  4374  -      91    1846    4258    4309  { 4310}
Sector    91  -    4374  
Sector  1846  -    3537    4374  
Sector  4258  -    3230    4374  
Sector  4309  -     919    2314    4374  
Sector  3537  -    1846  
Sector  3230  -    4258    4505  
Sector   919  -    4309  
Sector  2314  -    3186    4309  
Sector  4505  -    3230  
Sector  3186  -    2314  { 3901}
Sector  3901  -  < 3873>    623     660    1545    1969    3186  

--------------------------------------------------------------------------------

The first line says how many sectors are in the bubble, and if there's one 
entrance, displays that.  If there is more than one entrance, they are 
displayed on the second line, wrapping as needed to additional lines.

After that, the sectors in the bubble are displayed, wrapping as needed, in 
summary.

The next part is a list of all sector bubbles (including entrances, this 
time), and their warps.

Sectors surrounded by <>'s denote one-way in-warps.

Sectors surrounded by ()'s denote one-way out-warps.

Sectors surrounded by []'s denote unexplored sectors.

Sectors surrounded by {}'s denote bubble entrances.

Unembellished sectors are both out- and in-warps.

I've determined that properly displaying all the possible bubbles is 
virtually impossible with stream I/O, so a formatted display would require 

                                   Page 10
drawing a bitmap of sorts.  I might write such a thing, if I can figure out 
how, and use the data above to do it.  Anyone else might want to try the 
same thing.

Short of that, drawing on a piece of paper and connecting the lines is 
fairly easy given the above.  Those using TW Helper can do a /G command 
for a sector in the middle of the bubble to get a nice graphical layout.  
TWAR for Windows has a similar mode (currently at alpha level), and TWATS 
may very well have one as well.

For the smaller bubbles, that is.  I have found a bubble as large as 198 
sectors, with nine entrances, from a 20000-sector Gold game. Short of a 
graphical scrolling display, getting a visual grip on that one will be 
nearly impossible.

Note:  With the new feature of finding potential bubbles based on zero-turn
mapping data (CIM course plots), the bubble display will likely be riddled
with sectors surrounded by []'s, denoting that they are unexplored.  This
is normal, and it does in fact mean that the bubble is potentially
unreliable.  Since those sectors aren't actually explored, the information
about their outwarps is not guaranteed to be complete.  All it takes is one
unknown outwarp to completely kill a bubble.

Note:  If you use the /F switch to search for fake bubbles, the first line
will look instead like this:

12-sector bogus bubble with entrance at 2381.

When you see that header, there will necessarily be a sector in the bubble
with a warp shown with <>'s around it, denoting the sector number which has
a one-way warp into the bubble, behind the entrance.

=============================================================================

VI. Limitations

The program was written to accommodate up to 65,535 sectors, since the Gold 
version of TW currently supports up to 20,000.  In the unlikely event that
the game ever exceeds 65,535 sectors, it would not be very difficult to
change datatypes to long integers to increase capacity (to over 4 billion
sectors - though obviously a substantial machine would be required for
this).

The 16-bit DOS version has an absolute sector limit of 16382.  Whether it 
will run to completion depends on the available memory, the search 
parameters, and the number of bubbles in the universe matching those 
parameters.

The DPMI, OS/2, Linux, and Win32 executables will handle the program design
limits.

=============================================================================

VII. Performance

Over the course of this program's development, I've gained a lot of

                                   Page 11
experience as a programmer.  As a result, this program is reasonably
efficient by this point, though there's almost certainly room for
improvement here and there.  On fast machines, you won't notice.

The program is processor-bound, so your memory and disk subsystems are 
insignificant.  Your video subsystem may also have an impact, especially if 
running in a windowed session of whatever operating system you're using.  
Time the execution with output redirected to nul, and you'll see the 
difference.

The greater the maximum number of sectors, of course, the longer it will 
take to run.  The greater the number of entrances to search for, the longer 
it will take to run.  And less obviously, the more information about the
universe you have, the longer it will take to run.

================================================================================

VIII. Notes on Program Behavior

1)  The program does consider one-way exits into explored sectors the end of 
a bubble extent.  It's conceivable that such outgoing warps lead to more 
isolated sectors, something like this:

             [sector]
                |
[entrance] - [sector] - [sector] - [sector] -> [sector] 
                                                  |
                                               [sector] -> [universe]

Where -> denotes a one-way warp.  

In this case, that section between the two one-way warps would not be 
counted as part of the bubble.  However, provided there were enough such 
sectors for the given parameters, they would be part of a separate bubble 
beginning with the sector after the first one-way warp.  

I personally think that since those sectors have no path back into the 
bubble except through the universe, they shouldn't be considered part of it 
anyway.  If they did have a way back into the bubble, they'd be found and 
counted in the first place, because one-way inwarps are added to the 
bubble.

2)  Due to the way the program works, the following is considered a bubble:

           [universe]
               |
[sector] - [entrance] - [sector] - [sector] - [sector]
               |
           [universe]

Where the first sector is a single dead-end off of the entrance.  I'd 
personally not consider it part of the bubble, but I'll leave that to the 
user to decide.  The issue becomes very complex when considering the 
programmatic exclusion of such constructs.

When more than one entrance is tested for, the degree of this convolution 

                                   Page 12
can increase.  All that can be guaranteed is that all sectors reported as 
in the bubble are isolated from the universe by the entrances.

Note:  This is not applicable when using the /t option, which will not 
allow bubble sectors to be separated by the primary entrance.

3)  When using standard CIM sector information, the bubble search bases
whether or not a sector is reliable only on whether or not it's explored.
As a result, the less data you have, the less bubbles you find.  But when
you're using course plot information, the search algorithm has to consider
as reliable any sector which has at least one outwarp defined for it.
Because of this, the opposite effect is true - the less dat, the more
bubbles you find.  The more faulty bubbles, that is.

If the search is at a point where only one sector is left to check, and it
has three outwarps defined, all of which lead to dead ends, you'll have a
bubble (provided it meets the search criteria).  But if that sector has an
outwarp that wasn't discovered during the course plot session, it'll be
just another link in the universe.

Even more so than usual, you'll need to check the reality of any found
bubbles by exploring all the sectors involved, and using avoids to check
for one-way sectors leading into the bubble.

See the section on input file formats for details on how to maximize the
reliability of your course plots.

4)  The fake bubble option makes a fairly simple change to the existing
algorithm:  Instead of adding one-way inwarps to the bubble, they are
excluded, and the bubble is marked as potentially bogus.  When it comes
time to save the bubble, any which aren't so marked are discarded.  Then if
the bubble has at least one sector with at least one inwarp that is oneway,
and not coming from a sector that's inside the bubble, it's saved.
The nature of the program is to consider as an entrance the sector(s)
having one or more connections to the outside universe.  Some people might
consider the first sector with no connection to the universe, except via
the entrance(s), to be the entrance, where the front-line defenses are
placed.  Some bogus bubbles may have the one-way entrance leading to this
sector, which gives you no advantage if the person has the defenses here. I
myself tend to use that strategy, so that someone doesn't run into my
defense except if plotting a course into my bubble.  If you put your
defenses in the entrance sector(s), someone could run into them with a
normal course plot.  It's because so many people don't care about that, and
put their defenses in the entrance(s) that bubbles are still considered
bogus when the one-way entrance leads to the first non-entrance sector(s).

=============================================================================

IX. How it Works

Here's the basic logic of how it works:

1)  For each sector, treat one or more outgoing warps as potential parts of 
a bubble with the current sector as an entrance.  Treat the rest of the 
outgoing warps as the way back to the rest of the universe.


                                   Page 13
2)  Each possible combination of the situation in 1 should be tested.  The 
number of combinations for N outgoing warps is 2 to the Nth power minus 2 
(the two cases where either all sectors would be potential bubble members, 
or all sectors the way back to the universe).  If the /t option is used, 
then the number of combinations is simply N, as only one outgoing warp is
considered part of the potential bubble.

3)  Put each potential bubble sector into a bubble structure.

4)  Loop through the bubble structure, adding all non-oneway outgoing and 
oneway incoming warps to the end of it (note:  the /f option ignores
one-way incoming warps to find bogus bubbles).  If multiple entrances are
being checked for, then whenever the bubble cursor exceeds the minimum
number of sectors, and the remaining sectors in the bubble do not exceed
the maximum number of entrances, the bubble is added.  This will make for a
lot of extra bubbles, that are later trimmed out.  The alternative approach
is to do an outer loop for each entrance, which takes hours for two
entrances, and hundreds of thousands of years for five entrances.  This
method takes barely more than single-entrance searches.  Starting with
versions 0.14, the difference is really minimal.  With /E5 /Z5 tacked onto
the end of a /T /X150 search, the run speed increased only by about 5%
(using the /G switch reduces the increase even further).

5)  If the number of sectors in the structure exceed the maximum number of 
bubble sectors to search for, abort this iteration, and go on with the next 
possible bubble structure based on the current sector.

6)  If the end of the bubble structure is reached before the max sectors 
are exceeded, that means dead-ends have been reached at all fronts, and the 
bubble is indeed isolated from the universe by the entrance.  If the number 
of sectors is larger than the minimum sectors indicated, save the bubble.

7)  After all sectors have been processed, go through all the saved 
bubbles, and eliminate any duplicates and those which are part of larger 
bubble structures.

8)  Print out the information (currently in a lame format).

================================================================================

X. Compiling the Program

The source for the program is included in the 'source.zip' archive.

The language is C++, and I've tried to make the program cross-platform, 
though it may or may not be necessary to make some small modifications 
before it will compile for you. 

There are a few defines in place that were necessary to make it compile 
under the compilers I've been using.  These may or may not need to be 
removed or altered to allow compilation on other compilers, for other 
platforms.

There's nothing sneaky going on, so just compile each .cpp file, and link 
all the objects together as one executable.  I keep separate sources for 
ease of editing.  There are makefiles for all the compilers that I used 

                                   Page 14
included.

The five included executables are:

twbfos2.exe  - 32-bit OS/2 VIO executable 
twbfdpmi.exe - 32-bit DPMI executable
twbflin      - 32-bit Linux ELF executable
twbfw32.exe  - 32-bit Win32 console executable
twbfdos.exe  - 16-bit DOS executable (8086 instruction set)

The first was compiled with IBM VisualAge C++ 3.08 for OS/2, the second 
with the DJGPP package (a DOS port of GCC), the third with EGCS, the fourth
with Mingw32/EGCS, and the fifth with an old copy of Borland C++ 3.0 for
DOS.

=============================================================================

XI. Author Information

The "I" all through the rest of this file refers to me, Mike Ruskai, and I 
can be reached via e-mail to thannymeister@yahoo.com, should you have a 
question, suggestion, or problem report.

=============================================================================

XII. History

10-11-98 - Initial 0.01 release.

10-13-98 - Forgot to check one memory allocation pointer, so it would crash 
           if the allocation failed.  Fixed this.

10-17-98 - Reorganized the source, putting stuff from main() into objects,
           to better facilitate any future expansion efforts.  Altered the
           output format to report all data concerning the connectivity of
           the bubble sectors, though it's not formatted to be visually
           meaningful.  Fixed an obscure glitch that would prevent some
           bubbles from being reported, due to a false assumption I made
           earlier.  Release this as version 0.02.

10-19-98 - Put a check in for duplicate sector data, so if you accidentally
           append a sector report to an existing one, instead of 
           overwriting it, the program will not get screwed up.  Release
           this as version 0.03.

10-20-98 - Fixed the comparisons to properly reflect minimum and maximum 
           sectors in bubbles.  Version 0.04, just to have a number.

10-22-98 - Got a hold of the DJGPP compiler, so we now have a DPMI 
           executable in the archive, that will handle any amount of 
           sectors.  A few minor source changes, nothing that affects
           functionality.  Call this version 0.05.

10-23-98 - Fixed stupid memory leak.  The DOS version should work OK with
           any maximum bubble size value for 5000 sectors, now, though it's 
           pretty slow doing it.  Made some source changes that should

                                   Page 15
           hopefully make it easier to compiler on other platforms.  We'll 
           call this version 0.06.

11-30-98 - Added the ability to abort a search and have all bubbles found 
           to that point trimmed and saved by pressing the space bar.

           Added priority control for the OS/2 version.  This makes it 
           possible to cripple your machine fairly well, by specifying
           priority class 3 (time critical).  Added a DosSleep() call every
           100 sectors if that's the case, so that the program can be 
           aborted.  The effect is that running with time critical will be
           slower than normal priority, unless you've a lot of 
           high-priority programs already hogging the system, in which case
           time critical priority will allow it to run normally.  The given
           priority is not set until the bubble search commences.  The 
           loading of warp information, and setting of one-way warps takes
           place at normal priority.  The idea there is to put a long 
           search at idle priority, to run in the background (/p1 /d31 is 
           the recommended setting for this).

           Added the ability to search for multiple-entrance bubbles.  This
           was inspired by the feature in TW Gold of explicitly creating
           bubbles at Big Bang, which could have several entrances.  
           There's no theoretical limit to the number of entrances that can 
           be searched for, but I've put an arbitrary limit of 50 on the 
           program, since anything above that is of extremely dubious 
           utility.

           Modified the output format to wrap lines, instead of putting 
           sectors on one long line.  

12-05-98   Gave up on the idea of including a Win32 console executable, 
           since it (compiled with EGCS using Mingw32) was too bulky and 
           slow to be of any use.  This is version 0.07.

01-08-99   Added the /t option to alter the way bubbles are searched for.
           Instead of considering all possible combinations of warps as 
           either ways back to the universe or parts of the potential 
           bubble, only one warp at a time is considered part of the 
           potential bubble.  This makes runtime a little bit faster, and 
           eliminates the possibility of finding bubbles that are split by
           the primary entrance, as explained in the second note on program 
           behavior.  This is version 0.08.

01-11-99   Changed the way sector data is stored so that the DOS version 
           now has a sector limit of 16382, instead of 5460.  Version 0.09
           will be the moniker for this puppy.

01-29-99   Replaced iterative loops with memcpy() calls, after realizing 
           that using the same pointers is not a problem.  This speeds 
           things up quite a bit when doing large searches.

           Changed the multiple-entrance support so that it wouldn't bother
           saving bubbles that didn't have twice as many sectors as the 
           number of entrances.  Then I added the /z parameter to allow the 
           user to define the multiplier (minimum is 2, maximum is 1000).  

                                   Page 16
           The result, even with just a multiplier of 2, is dramatically 
           faster multiple-entrance searches, with less garbage bubbles.  
           Setting this to a value of 10 or more will make sure that only 
           viable multiple-entrance bubbles are found, such as 20-sector 
           bubbles with 2 entrances, or 100-sector bubbles with 10 
           entrances; each being the equivalent of a single-entrance 
           10-sector bubble in terms of how much is protected per defended 
           sector.

           This is version 0.10.

03-11-99   Did a bit of optimizing, primarily by inlining small functions.

           Added file read/write error checking, just in case.

           This is version 0.11.

08-17-99   No real changes.  Just updating the e-mail address.

           Nevertheless, this is 0.12.

01-28-00   At the suggestion of a program user, added the ability to read
           in data captured by the user, doing CIM course plots.  This
           allows a pseudo-exploration of the universe for the purpose of
           finding likely bubbles to be actually explored.  The /W option
           is used to specify the capture file.

           Along with this, I added a binary sector database option, which
           will keep track of the outgoing warps that have been discovered
           using one or many CIM course plot sessions.  It will also keep
           track of whether or not the sectors are actually explored.  The
           /B option is used to specify this file.

           Added the /U option to allow updating the binary database
           without performing a bubble search.

           Added the /A option to use the old program behavior of avoiding
           unexplored sectors when searching for bubbles.  This allows you
           to use a binary database containing warp information for
           unexplored sectors without getting possibly unreliable search
           results.  Obviously, this is for when you've done actual
           exploration, and aren't trying to find potential bubbles using
           CIM course plots.

           The OS/2 executable is now compatible with only OS/2 Warp and
           above, because the code is compressed as well as the data.  In
           the unlikely event that someone with OS/2 2.x wants to run this
           program, they can uncompress and recompress it using the lxLite
           utility (use the /c:ver2x switch).

           Made a few changes necessary to compile a Linux version.  The
           Linux executable is different from the others in one respect - a
           keypress (to abort and save whatever bubbles have been found) is
           only checked for every 50 sectors, because the method of
           determining whether there's a keypress waiting or not in Linux
           is very slow.

                                   Page 17

           This is version 0.13.

02-03-00   Added ability to read a second binary file, for the purposes of
           combining the information contained in them.  This file is
           specified with the /C switch.  Though the program will simply
           treat it as another input file, the intended usage is something
           like this:

                twbfind /n5000 /bgame.dat /cauxdata.dat /u

           That would read in game.dat, then read in auxdata.dat, and write
           the information collected from both back to game.dat.  Two
           conditions will clue you in that the two data files are from
           different universes:

                1)  You get an error saying more than 6 warps were found
                    for a given sector.

                2)  You get an error about an integer being too large while
                    reading the second binary file.

           If using the new binary formt (see next comment), the size of
           the universe is stored at the front of the file, and any
           difference will be noted immediately.

           Changed the binary format somewhat, to allow for a 16-byte
           header at the beginning of the file.  The header contains a
           64-bit signature, to verify during read that the file is valid;
           the major and minor version level of the release of TWBFind that
           created the file, to allow for future changes; the size of the
           universe; and some reserved space for future additions.  The
           data itself is also altered a bit (see the options section for
           the details of how it's stored), to the point where adding the
           ability to read the old files is too much of a pain.  I created
           a conversion program, which can be downloaded in a separate
           archive (twbfcvt.zip), that will convert from the old to the
           new format.  With the new format, any time you specify an
           existing binary file as input, you don't need to specify the
           number of sectors in the universe on the command line (if you
           do, it will be overridden by the info in the binary file).

           In a trend that's sure to continue, I ripped off a neat idea
           from a program called TW Guru (the author of which is nowhere to
           be found).  If you use the /F switch, you will find fake bubbles
           instead of real ones.  That is, a bubble which appears kosher
           from the inside, but has a one-way sector going into it behind
           the entrance.  This function will be very useful for finding
           people who aren't scrupulous about checking the validity of the
           bubble(s) they find.  The best ones have the one-way entrance
           towards the back, where the least defended planets will likely
           be.

           I made two performance enhancements.  The first one was to
           change the bubbleset from a dynamically expanding array to a
           fixed-length array, the length of which is determined at run

                                   Page 18
           time.  The default length is 1024 bubbles, which is enough for
           any reasonable search.  This can be overridden with the /R
           switch.  For the included executables, the memory required is
           4 bytes per bubble (the size of a memory pointer).  The
           fixed-length array helps, of course, be preventing the need to
           allocate new memory, and copy all the bubbles to the new
           location, each time one was found and added.

           The second performance enhancement is only in effect when you
           use the /G switch, which tells the program to gobble up more
           memory to run faster.  When this is done, new bubble objects
           don't use dynamically sized arrays, but instead allocate enough
           memory at initialization to contain the largest allowable
           bubble (determined by /X and /E).  This negates the need to
           allocate memory and copy over data when adding sectors and
           entrances.  With search parameters of /M3 /X100 /E4 /Z3 on a
           5000-sector universe, the result was an additional 116KB of
           memory required during operation, and a 20% reduction in search
           time.  With /T /X25, the increase in memory requirements wasn't
           detectable, but the run time went down by over 30%, so this
           option is useful for even small searches on memory-tight
           machines.

           The DOS, DPMI, and Linux executables are now compressed with
           UPX.  This improves on PKLITE and DJP for the first two,
           respectively.

           I added a Win32 executable, using Mingw32/EGCS, which has
           improved quite a bit since I last tried it.  The executable
           speed is pretty good, even though I can't get rid of the
           annoying mouse cursor, or even the text cursor (the standard
           Win32 calls to do the latter simply don't work).  UPX supports
           PE compression, but a program called EZIP did a much better job
           (less than half the size of UPX's compressed EXE).  A bug
           somewhere in Mingw32 package (or perhaps Win95) causes the
           program to crash when you press CTRL-C (presumably at exit()).





















                                   Page 20
